package com.bichengcao.googlecodejam.round1b2008;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public class NumberSets {

	static int N;

	public static void main(String[] args) throws IOException {
		Input[] inputs = parseInput("src/com/bichengcao/googlecodejam/round1b2008/B-large-practice.in");
		Output[] outputs = process(inputs);
		writeOutput("src/com/bichengcao/googlecodejam/round1b2008/NumberSets.out", outputs);
	}

	static class Input {

		long a, b, p;
	}

	static class Output {

		int result;
	}

	private static Input[] parseInput(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		N = Integer.parseInt(in.readLine());
		Input[] array = new Input[N];

		for (int i = 0; i < N; i++) {
			Input input = array[i] = new Input();
			String line = in.readLine();
			String[] splits = line.split(" ");
			input.a = Long.parseLong(splits[0]);
			input.b = Long.parseLong(splits[1]);
			input.p = Long.parseLong(splits[2]);
		}

		in.close();
		return array;
	}

	static int index = 0;
	static int[] primes = new int[100000];

	private static Output[] process(Input[] inputs) {
		Output[] outputs = new Output[N];

		// cache all primes under 1000000
		for (int i = 2; i <= 1000000; i++) {
			boolean isPrime = true;
			for (int j = 0; j < index; j++) {
				if (i % primes[j] == 0) {
					isPrime = false;
					break;
				}
			}
			if (isPrime) {
				primes[index++] = i;
			}
		}

		for (int i = 0; i < N; i++) {
			outputs[i] = process(inputs[i]);
		}
		return outputs;
	}

	private static Output process(Input input) {
		Output output = new Output();

		int n = (int) (input.b - input.a + 1);
		int[] set = new int[n];
		for (int i = 0; i < n; i++) {
			set[i] = i;
		}
		for (int i = 0; i < index; i++) {
			if (primes[i] >= n) {
				break;
			}
			if (primes[i] < input.p) {
				continue;
			}
			int start = (int) (((input.a - 1) / primes[i] + 1) * primes[i] - input.a);
			int t = start;
			int depth = 0;
			while (set[t] != t) {
				t = set[t];
				depth++;
			}
			int x = start + primes[i];
			while (x < n) {
				int temp = x;
				int tempd = 0;
				while (set[temp] != temp) {
					temp = set[temp];
					tempd++;
				}
				if (t != temp) {
					if (tempd <= depth) {
						set[temp] = t;
					} else {
						set[t] = temp;
						t = temp;
					}
				}

				x += primes[i];
			}
		}
		for (int i = 0; i < n; i++) {
			if (i == set[i]) {
				output.result++;
			}
		}

		return output;
	}

	private static void writeOutput(String filename, Output[] outputs) throws IOException {
		PrintWriter out = new PrintWriter(new FileWriter(filename));
		for (int i = 0; i < N; i++) {
			out.println("Case #" + (i + 1) + ": " + outputs[i].result);
		}
		out.close();
	}

}
